二分查找
二分查找
什么是二分查找
又叫折半查找,是一种效率高效的查找方法
原理:将数组分为三部分,依次是中值前、中值、中值后。将要查找的值和中值比较,若小于中值则在中值前找,若大于中值则在中值后面找,等于中值时直接返回
二分查找的前提
- 必须采用顺序存储结构
- 必须按关键字大小有序排列
代码实现(递归版)
def binary_search(alist, item):
"""二分查找"""
# 数列的长度
n = len(alist)
# 递归的结束条件
if n == 0:
return False
# 中间值 // 整除
mid = n // 2
if item == alist[mid]:
return True
elif item < alist[mid]:
return binary_search(alist[0:mid], item) # 注意要加return 否则最终的查找结果是None, return不具有向上的传递性
elif item > alist[mid]:
return binary_search(alist[mid + 1:], item) # 注意要加return 否则最终的查找结果是None
if __name__ == '__main__':
alist = [1, 2, 3, 4, 5]
print(binary_search(alist, 1))
print(binary_search(alist, 6))
代码实现(非递归版)
def binary_search(alist, item):
"""二分查找"""
# 设置起始位置 获取中间值
start = 0
end = (len(alist) - 1)
while start <= end:
# 获取中间值
mid = (start + end) // 2
if item == alist[mid]:
return True
elif item < alist[mid]:
end = mid - 1
elif item > alist[mid]:
start = mid + 1
# 没有找到想要找的数字
return False
if __name__ == '__main__':
alist = [1, 2, 3, 4, 5]
print(binary_search(alist, 3)) # True
print(binary_search(alist, 9)) # False
Java版实现(非递归版)
/*1. 定义两个变量,表示要查找的范围,默认min=0, max=最大索引
2. 循环查找,但是min <= max
3. 计算出mid的值
4. 判断mid位置的元素是否为要查找的元素,如果是直接返回对应索引
5. 如果要查找的值在mid的左半边,那么min值不变,max = mid -1, 继续下次循环查找
6. 如果要查找的值在mid的右半边,那么max值不变,min = mid + 1, 继续下次循环查找
7. 当min > max时,表示要查找的元素在数组中不存在,返回-1. */*
public static int binarySearchForIndex(int[] arr, int number) {
// 1. 定义查找的范围
int min = 0;
int max = arr.length - 1;
// 2.循环查找 min <= max
while(min <= max){
// 3. 计算出中间位置mid
int mid = (min + max) / 2;
// mid指向的元素 > number
if (arr[mid] > number){
// 表示要查找的元素在左边
max = mid - 1;
}else if (arr[mid] < number){
// mid指向的元素 < number
// 表示要查找的元素在右边
min = mid + 1;
}else{
// mid指向的元素 == number
return mid;
}
}
// 如果min大于了max就表示元素不存在,返回-1
return -1;
}
二分查找时间复杂度
最差时间复杂度:
最优时间复杂度: